package a2022.a20220920;

import java.util.Arrays;

/**
 * @author lenovo
 * @date 2022/9/20
 */
public class a {
    public static void main(String[] args) {
        System.out.println(canPartitionKSubsets(
                new int[]{4,4,6,2,3,8,10,2,10,7},
                4));
    }

    public static boolean canPartitionKSubsets2(int[] nums, int k) {
        Arrays.sort(nums);
        int num = 0;
        for (int i = 0; i < nums.length; i++) {
            num += nums[i];
        }
        if (num % k != 0) return false;
        int a = num / k;
        //双指针遍历
        int left = 0, right = nums.length - 1;
        if (nums[right] > a) return false;
        num = nums[right];
        while (left < right) {
            if (num > a) {
                return false;
            } else if (num < a) {
                num += nums[left];
                left++;
            }else {
                right--;
                num = nums[right];
            }
        }
        return true;
    }



    public static boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) sum += nums[i];
        if (sum % k != 0) return false;
        int target = sum / k;
        // 排序优化
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            l++;
            r--;
        }
        return backtrack(nums, 0, new int[k], k, target);
    }
    /**
     *
     * @param nums 原始数组
     * @param index 第 index 个球开始做选择
     * @param bucket 桶
     * @param k 个数
     * @param target 容量
     * @return
     */
    private static boolean backtrack(int[] nums, int index, int[] bucket, int k, int target) {
        // 结束条件优化
        if (index == nums.length) return true;
        for (int i = 0; i < k; i++) {
            // 优化点二
            if (i > 0 && bucket[i] == bucket[i - 1]) continue;
            // 剪枝
            if (bucket[i] + nums[index] > target) continue;
            bucket[i] += nums[index];
            if (backtrack(nums, index + 1, bucket, k, target)) return true;
            bucket[i] -= nums[index];
        }
        return false;
    }



}
